package ru.ifmo.trafficspy.analyzer.clustering;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class ClusterizerFactory {
	
	private static class Edge {
		final int u;
		private final int v;
		final double w;
		
		public Edge(int u, int v, double w) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
		
	}
	
	public static KMeansClusterizer getKMeansClusterizer(double[] values, int clusterCnt) {
		int n = values.length;
		if (clusterCnt > n) {
			throw new IllegalArgumentException(String.format("Too many clusters: clusterCnt = %d, values.length = %d", clusterCnt, n));
		}
		
		double[] point = values.clone();
		Arrays.sort(point);
		
		Edge[] edges = new Edge[n - 1];
		for (int i = 0; i < n - 1; i++) {
			edges[i] = new Edge(i, i + 1, point[i + 1] - point[i]);
		}
		
		Arrays.sort(edges, new Comparator<Edge>() {
			public int compare(Edge o1, Edge o2) {
				return Double.compare(o1.w, o2.w);
			}
		});
		
		boolean[] hasEdgeForward = new boolean[n];
		for (int i = 0; i < n - clusterCnt; i++) {
			hasEdgeForward[edges[i].u] = true;
		}
		
		int[] point2cluster = new int[n];
		int[] clusterSize = new int[clusterCnt];
		double[] clusterCenter = new double[clusterCnt];
		int curCluster = 0;
		{
			int i = 0;
			while (i < n) {
				int j = i;
				while (hasEdgeForward[j]) {
					j++;
				}
				for (int k = i; k <= j; k++) {
					point2cluster[k] = curCluster;
					clusterSize[curCluster]++;
					clusterCenter[curCluster] += point[k];
				}
				clusterCenter[curCluster] /= clusterSize[curCluster];
				i = j + 1;
				curCluster++;
			}
		}
		
		while (true) {
			boolean done = true;
			int[] newPoint2cluster = new int[n];
			for (int i = 0; i < n; i++) {
				double min = Double.POSITIVE_INFINITY;
				int minj = -1;
				for (int j = 0; j < clusterCnt; j++) {
					double cd = Math.abs(point[i] - clusterCenter[j]);
					if (cd < min) {
						min = cd;
						minj = j;
					}
				}
				newPoint2cluster[i] = minj;
				done &= minj == point2cluster[i];
			}
			if (done) {
				break;
			}
			point2cluster = newPoint2cluster;
			for (int i = 0; i < clusterCnt; i++) {
				int cnt = 0;
				double sum = 0;
				for (int j = 0; j < n; j++) {
					if (point2cluster[j] == i) {
						cnt++;
						sum += point[i];
					}
				}
				clusterCenter[i] = sum / cnt;
			}
		}
		
		return new KMeansClusterizer(clusterCenter);
	}
}
